package com.example.red_black_tree;

/**
 * @ClassName RBT
 * @Description TODO
 * @Author: XMK
 * @Date: 2021/1/7 20:25
 * @Version: 1.0
 */
public class RBT {

    public void insertNode(Node n) {
        insertCase1(n);
    }

    private void insertCase1(Node n) {
        if (n.parent == null) {
            n.isBlack = true;
        } else {
            insertCase2(n);
        }
    }

    // Case 2：父节点是黑色
    private void insertCase2(Node n) {
        if (n.parent.isBlack) {
            return;
        } else {
            insertCase3(n);
        }
    }

    // Case 3：父节点和叔节点都是红色
    private void insertCase3(Node n) {
        Node uncle = n.uncle;
        if (uncle != null && !uncle.isBlack) {
            n.parent.isBlack = true;
            uncle.isBlack = true;
            Node grandParent = n.grandparent;
            grandParent.isBlack = false;
            insertCase1(grandParent);
        } else {
            insertCase4(n);
        }
    }

    // Case 4：N的父节点为红色，叔节点为黑色
    private void insertCase4(Node n) {
        Node g = n.grandparent;
        if (n == n.parent.right && n.parent == g.left) {  // N为长子，且父节点为祖节点的次子
            n.parent.rotateLeft();
            n = n.left;
        } else if (n == n.parent.left && n.parent == g.right) {  // N为次子，且父节点为祖节点的长子
            n.parent.rotateRight();
            n = n.right;
        }
        insertCase5(n);
    }

    // Case 5：N的父节点为红色，叔节点为黑色
    private void insertCase5(Node n) {
        Node p = n.grandparent;
        p.isBlack = false;
        n.parent.isBlack = true;
        if (n == n.parent.left) {  // N为次子，且父节点也是祖节点的次子
            p.rotateRight();
        } else {
            p.rotateLeft();
        }
    }
}
